# !/usr/bin/env python
# -*-coding:utf-8 -*-
"""
@Author : Ayao
@Time   : 2022/5/28
@File   : 在排序数组中查找元素的第一个和最后一个位置.py
"""

# https://leetcode.cn/leetbook/read/binary-search/xenp13/
from typing import List


class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        if len(nums) == 0:
            return [-1, -1]
        left, right = 0, len(nums) - 1
        while left + 1 < right:
            mid = left + (right - left) // 2
            if nums[mid] < target:
                left = mid
            if nums[mid] >= target:
                right = mid
        if nums[left] == target:
            l = left
        elif nums[right] == target:
            l = right
        else:
            return [-1, -1]

        left, right = 0, len(nums) - 1
        while left + 1 < right:
            mid = left + (right - left) // 2
            if nums[mid] > target:
                right = mid
            if nums[mid] <= target:
                left = mid
        if nums[right] == target:
            return [l, right]
        else:
            return [l, left]


nums = [5, 7, 7, 8, 8, 10]
target = 8
print(Solution().searchRange(nums, 8))
